package DataStructure.linkList.swordOffer;

import DataStructure.linkList.ListNode;

/**
 * 剑指 Offer 52. 两个链表的第一个公共节点 https://leetcode.cn/problems/liang-ge-lian-biao-de-di-yi-ge-gong-gong-jie-dian-lcof
 * 题目简述：给你两个单链表的头节点headA和headB，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回null。
 */
public class GetIntersectionNode {

    /**
     * 思路：双指针，p1和p2各自从A、B链表头同时出发，p1遍历完A链表后继续遍历B链表，p2遍历完B链表后继续遍历A链表，
     * 若存在交点则p1和p2会在链表交点处相遇，若不存在交点则最终p1和p2会同时指向null
     */
    ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode p1 = headA, p2 = headB;
        while (p1 != p2) {
            p1 = p1 == null ? headB : p1.next;
            p2 = p2 == null ? headA : p2.next;
        }
        return p1;
    }
}
